home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / prio / _m_heap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  2.7 KB  |  131 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _m_heap.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/impl/m_heap.h>
  17.  
  18. m_heap::m_heap(int m)
  19. { if (m<=0) error_handler(1,string("m_heap constructor: illegal size = %d",m));
  20.   count = 0;
  21.   start = 0;
  22.   offset = 0;
  23.   M = m+1;
  24.   T = new list_item[M+1];
  25.   for(int i=0; i<=M; i++) T[i] = L.append(GenPtr(MAXINT));
  26. }
  27.  
  28. void m_heap::clear()
  29. { L.clear();
  30.   for(int i=0; i<=M; i++) T[i] = L.append(GenPtr(MAXINT));
  31.   count = 0;
  32.   start = 0;
  33.   offset = 0;
  34. } 
  35.  
  36. m_heap_item m_heap::first_item() const
  37. { list_item it = L.first();
  38.   while (it && L.inf(it) == GenPtr(MAXINT)) it = L.succ(it);
  39.   return it;
  40.  }
  41.   
  42. m_heap_item m_heap::next_item(m_heap_item it) const
  43. { it = L.succ(it);
  44.   while (it && L.inf(it) == GenPtr(MAXINT)) it = L.succ(it);
  45.   return it;
  46.  }
  47.  
  48. m_heap_item m_heap::insert(GenPtr kk, GenPtr info)   // int key
  49. { int key = int(kk);
  50.   int k;
  51.   if (count)
  52.    { find_min();
  53.      k = key-offset; 
  54.     }
  55.   else 
  56.    { start = key%M;
  57.      k = 0;
  58.      offset = key;
  59.     }
  60.  
  61.   if (k<0 || k>=M) 
  62.    error_handler(1,string("m_heap insert: illegal key %d \n",key));
  63.  
  64.   copy_inf(info);
  65.  
  66.   count++;
  67.   return L.insert(info,T[(start+k)%M]); 
  68. }
  69.  
  70. m_heap_item m_heap::find_min() const
  71. { if (count)
  72.   { while (L.succ(T[start])==T[start+1])
  73.     { (*(int*)&offset)++;
  74.       (*(int*)&start)++;
  75.       if (start == M) (*(int*)&start) = 0;
  76.      }
  77.     return L.succ(T[start]);
  78.    }
  79.  else return 0;
  80. }
  81.  
  82. GenPtr m_heap::del_min()
  83. { if (count)
  84.    { find_min();
  85.      count--;
  86.      m_heap_item p = L.succ(T[start]);
  87.      GenPtr inf = L.contents(p);
  88.      L.del(p);
  89.      return inf;
  90.     }
  91.   else error_handler(1,"m_heap del_min: heap is empty");
  92.   return 0;
  93. }
  94.  
  95. void m_heap::del_item(m_heap_item it) 
  96. { GenPtr x = L.contents(it);
  97.   clear_inf(x);
  98.   L.del(it); 
  99.   count--;
  100. }
  101.  
  102. void m_heap::change_key(m_heap_item it, GenPtr kk)  // int key
  103. { int key = int(kk);
  104.   find_min();
  105.   GenPtr inf = L.contents(it);
  106.   L.del(it); 
  107.   int k = key - offset;
  108.   if (k<0 || k>=M) 
  109.    error_handler(1,string("m_heap change key: illegal key %d\n",key));
  110.   L.insert(inf,T[(start+k)%M]);
  111. }
  112.  
  113.  
  114. void m_heap::print() const
  115. { m_heap_item p;
  116.   cout << string("count = %d   start = %d   offset = %d\n",count,start,offset);
  117.   for (int i=0;i<M;i++) 
  118.   if (L.contents(L.succ(T[i])) != GenPtr(MAXINT))
  119.   { cout << string("%3d: ",i);
  120.     p = L.succ(T[i]);
  121.     while (L.contents(p) != GenPtr(MAXINT))
  122.      { cout << string("(%d) ",L.contents(p));
  123.        p = L.succ(p);
  124.       }
  125.    cout << "\n";
  126.    }
  127.    cout << "\n";
  128. }
  129.  
  130.  
  131.